package com.zzh.backtracking;
//给定一个 没有重复 数字的序列，返回其所有可能的全排列。
//
// 示例:
//
// 输入: [1,2,3]
//输出:
//[
//  [1,2,3],
//  [1,3,2],
//  [2,1,3],
//  [2,3,1],
//  [3,1,2],
//  [3,2,1]
//]
// Related Topics 回溯算法
// 👍 778 👎 0
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class No46_permute {
    public static void main(String[] args) {
        No46Solution solution = new No46Solution();
        solution.permuteUnique(new int[]{1,2,3,4});

    }
}
class No46Solution{
    private List<List<Integer>> lists= new ArrayList<List<Integer>>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        myDo(nums,0,nums.length-1);
        return lists;
    }
    public void myDo(int[] nums,int from,int to){
        if (from>=to){
            lists.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));

            System.out.println(Arrays.toString(nums));
            return;
        }
        for (int i=from;i<=to;i++){
            swap(nums,from,i);
            myDo(nums,from+1,to);
            swap(nums,from,i);
        }
    }
    public void swap(int[] nums,int from,int to){
       int temp=nums[from];
       nums[from]=nums[to];
       nums[to]=temp;
    }
}
